package impl;

import anaydis.sort.SorterType;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;


public class MergeSorterTopDown extends AbstractSorter {

    public MergeSorterTopDown() {
          super(SorterType.MERGE);
      }


    public <T> void sort(Comparator<T> comparator, List<T> list) {
        sort(comparator, list, 0, list.size() - 1);
    }

    private <T> void sort(Comparator<T> comparator, List<T> list, int left, int right) {
        if (right <= left) return;
        int m = (right + left) / 2;
        sort(comparator, list, left, m);
        sort(comparator, list, m + 1, right);
        Merge(comparator, list, left, m, right);
    }

    private <T> void Merge(Comparator<T> comparator, List<T> list, int left, int m, int right) {
        int i, j;
        List<T> aux = new ArrayList<T>();

        for (T t : list) {
            aux.add(t);
        }
        for (i = m + 1; i > left; i--) {
            aux.set(i - 1, list.get(i - 1));
        }
        for (j = m; j < right; j++) {
            aux.set(right + m - j, list.get(j + 1));
        }
        for (int k = left; k <= right; k++) {
            if (greater(comparator, aux, i, j)) {
                list.set(k, aux.get(j--));
            } else {
                list.set(k, aux.get(i++));
            }
        }
    }
}